package org.example.myleet.p875;

public class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int l = 1, r = Integer.MIN_VALUE, k, hours;
        for (int pile : piles) {
            r = Math.max(r, pile);
        }
        //二分法找答案，通过游标k（代表吃香蕉的速度）二分的方式，吃得快了则hours会更小，吃得慢了则hours会更大
        //通过二分跳跃的方式快速缩小结果的范围
        while (l < r) {
            k = (l + r) >> 1;
            hours = calculateHours(piles, k);
            if (hours == h) {
                r = k;
            }
            if (hours > h) {
                l = k + 1;
            } else {
                r = k;
            }
        }
        return l;
    }

    private int calculateHours(int[] piles, int k) {
        int hours = 0;
        for (int pile : piles) {
            //这里最容易想到的方法1是先计算取余，如果不是0则补1
            //后来我想到方法2是先计算整数除法结果，然后用乘法校验是否整除
            //官方的方法3是巧妙地给pile加上k-1，这样再做除法就可以一次得答案
            //方法3解析：若能整除，则(k-1)/k的结果<1而不会增加1；若不能整除，则(余数+k-1)/k则会>=1，变相给整数除法做到ceiling的效果
            hours += (pile + k - 1) / k;
        }
        return hours;
    }
}
